As circuits have become more complex, electronic design automation (EDA) software tools have been developed to facilitate designing, testing and modifying circuit designs in preparation for manufacturing (i.e., fabricating or otherwise producing) physical circuit structures that are based on final versions of the circuit designs. As used herein, the term “circuit” generally refers to integrated circuits (ICs), printed circuit boards (PCBs), and other types of electronic device at a system level, sub-system level, or even at a transistor level. EDA software tools typically include resources (e.g., standard-cell libraries) and design assembly software that allow circuit designers to efficiently arrange and interconnect the various functional sections (blocks) of their circuit designs in the form of software-based circuit descriptions, various testing resources that allow the circuit designers to test and modify their circuit designs during development, and various conversion tools that facilitate subsequent fabrication of physical circuits based on the final circuit designs. Because modern circuits (e.g., System-on-Chip devices) can include billions of transistors and other circuit elements, EDA tools have become essential in the development and testing of modern circuit designs. That is, without EDA software tools, generating a modern circuit from concept to physical circuit using manual design techniques would be virtually impossible.
Testing functions performed by EDA software tools typically include simulation-type functional verification (simulation), which allows circuit designers to simulate operation of their circuit designs in order to verify that the circuit design will function as intended. FIG. 28 is a block diagram showing portions of a greatly simplified EDA software tool 50 that are utilized to perform simulation on a circuit design 60, which is either generated using other portions (not shown) of EDA software tool 50, or transferred to EDA software tool 50 from another EDA software tool. As indicated in FIG. 28, simulation is typically performed using software tools known in the art as a test-bench (aka, “testbench”) 70 and a simulator 80, which are controlled during simulation by way of well-known user input/output interface devices 40. Test-bench 70 typically includes a stimulus (test) generator 72 that generates stimulus streams 73 in accordance with user-supplied test parameters (e.g., using a constraint solver), and a data analyzer 75 configured to collect and analyze response data transmitted from simulator 80. Simulator 80 is configured to store and emulate a circuit design model 65, which is a version of circuit design 60 that has been written in (or translated into) a specified software language understood by simulator 80, such as Verilog, VHDL or Spice. During simulation, simulator 80 receives the input stimulus streams 73 from stimulus generator 72, applies each input stimulus stream 73 to circuit design model 65 using known techniques, and outputs response data 74 indicating performance of circuit design model 65 in response to the applied stimulus stream 73. Data analyzer 75 receives response data 74 and, for example, compares the received response data with user-supplied expected response data, and generates a verification test result report 77 that is transmitted in a operable form to a user (e.g., the circuit designers tasked to develop circuit design 60) by way of I/O interface 40. In combination, test-bench 70 and simulator 80 provide EDA tool 50 with a versatile tool for functionally verifying the operation of circuit designs in a manner that allows circuit designers (users) to identify and correct flaws (bugs) in their circuit designs (e.g., circuit design 60) before incurring the significant expense of manufacturing physical circuits based on their circuit designs.
FIG. 29 is a diagram depicting an exemplary simplified stimulus stream 73 utilized during the exemplary simulation process depicted in FIG. 28. As mentioned above, stimulus stream 73 is made up of twelve test vector values V00 to V32 that are transmitted to corresponding nodes of circuit design model 65. During the generation of stimulus stream 73 by stimulus generator 72, test vector values V00 to V32 are often formatted in an array (matrix), which may be visually depicted by way arranging the test vector values in horizontal rows and vertical columns. As known in the art, this matrix arrangement facilitates the generation of stimulus streams that address various issues such as symmetry. That is, generating test vector values V00 to V32 using a matrix arrangement provides an effective mechanism for dealing with symmetry by way of applying one or more constraints to each row of test vector values, each column or test vector values, and/or each diagonal series of test vector values in the manner described below. Note that the array depicted in FIG. 29 is greatly simplified and generalized for purposes of brevity, and that an actual stimulus stream utilized during simulation of a practical circuit design may include hundreds or thousands of test vector values arranged in any number of rows and any number of columns, and each test vector value may include any number of sub-values arranged in one or more additional dimensions.
The stimulus generators used in conventional test-benches (e.g., stimulus generator 72 shown in FIG. 28) typically utilize two different methodologies to generate input stimuli for testing circuit design models: directed test methodologies, and constrained random test methodologies.
Directed test methodologies involve the generation of predefined stimulus streams that are designed to exercise specific functionalities in a target circuit design such that the target circuit design operates in a predictable manner. That is, directed test input stimuli is configured to evoke a predictable desired response by the target circuit design, whereby the target circuit design is considered acceptable when the actual directed test response data generated by the target circuit design model matches expected (predicted) response data. A benefit of utilizing directed test methodologies is that the corresponding simulation processes are able to provide reliable positive verification results (e.g., using the example of FIG. 28, when data analyzer 75 verifies that response data 74 matches the expected response data provided by a user, thereby confirming that circuit design model 65 accurately performed the corresponding required function). However, a problem with directed tests is that comprehensive input stimuli and corresponding predicted response requires many hours of preparation by a knowledgeable engineer. Moreover, because directed test methodologies focus on a narrow range of operating conditions, they are not able to provide reliable negative verification (i.e., feedback that concentrates on the identification and elimination of inadvertent functionality bugs). That is, directed test methodologies are not able to detect possible functional errors and problems that may arise when the circuit design is subjected to untested stimuli (e.g., when the circuit is subject to operating conditions other than those simulated during the directed test).
Constrained random test methodology utilizes a constraint solver to automatically generate stimulus streams that satisfy user-specified test vector value constraints. Test vector value constraints (referred to below as “constraints”) are usually specified as part of a test-bench program by knowledgeable personnel (e.g., a circuit designer/engineer), and serve to restrict one or more test vector values in a specified section of each valid stimulus stream. As used herein, the term “single-dimension constraints” generally refer to constraints that are directed to test vector values related to each other in a row dimension (referred to below as “row constraints”), a column dimension (referred to below as “column constraints”), or a diagonal-sequence dimension (referred to below as “diagonal constraints”). Referring again to FIG. 29, row constraints establish restrictions on each horizontally aligned series of test vector values in the stimulus stream array, column constraints establish restrictions on each vertically aligned series of test vector values, and diagonal constraints establish restrictions on diagonally aligned series of test vector values (referred to herein as “diagonals”). For example, a row constraint may restrict a sum of all test vector values in each row to a user-defined row-sum value, whereby stimulus stream 73 would comply with the row constraints only if a sum of the test vector values in each row (i.e., a sum of test vector values V00, V01 and V01, a sum of test vector values V10, V11 and V12, a sum of test vector values V20, V21 and V22, and a sum of test vector values V30, V31 and V32) is equal to the user-defined row-sum value. Similarly, a column constraint restricting the sum of each column to a user-defined column-sum value would require sums of the test vector values in each column (e.g., V00, V10, V20 and V30) to equal the user-defined column-sum value, and a diagonal constraint restricting the sum of each diagonal series of test vector values to a user-defined diagonal-sum value would require sums of the test vector values in each diagonal series (e.g., V20, V11 and V02) to equal the user-defined diagonal-sum value. In addition to row, column and diagonal dimensions, constraints may be placed on other dimensional aspects of a stimulus stream, such as constraints applied to a byte-value dimension (i.e., where each test vector value V00 to V32 includes a multiple-bit digital value, and one or more byte-value constraints establish restrictions on each multiple-bit digital value). As used herein, the phrase “multi-dimensional constraints” refers to a set including one or more constraints from each of two or more constraint types, such as those mentioned above.
The basic functionality of a constraint solver used for EDA software tool applications may be described by its ability to solve the following constraint satisfaction problem: given a set of user-provided global variable values that define the number and type of test vector values in each stimulus stream, and given a set of constraints that restrict interrelationships between associated test vector values in each stimulus stream, automatically generate multiple unique stimulus steams that satisfy the set of constraints. The number of test vector values in each data stream array may be determined by multiplying the number of test vector values in each row by the number of test vector values in each column. For example, in the simplified embodiment shown in FIG. 29, stimulus stream 73 includes three rows and four columns, yielding twelve test vector values. The “type” of test vector value refers to the range of different values that may be assigned to each test vector value (e.g., a binary-type test vector value may have either binary 1 or 0 values, whereas a byte-type test vector value may have 256 different values). As understood in the art, various constraint types and combinations of constraints may be applied to generate stimulus streams configured to produce various test results indicating corresponding positive or negative verification data. A key advantage of constrained random test methodologies over directed test approaches is that a large number of different stimulus streams can be generated in a substantially shorter amount of time than could be generated using directed test methods, thereby facilitating far more comprehensive functional verification data during a given development period than could be produced using directed text methodologies.
Conventional constraint solvers utilized in early EDA software tools were configured to solve most constraint problems using conventional decision procedures (e.g., Automatic Test Pattern Generation (ATPG) or satisfiability (SAT) algorithms), which are based on efficient backtracking techniques. A problem with these conventional constraint solvers is that conventional decision procedures do not work well when required to generate stimulus streams that comply with two or more constraints that are dependent on each other (i.e., where modifications to the test vector values of a stimulus stream that are required to satisfy one of the related constraints may cause the stimulus stream to be non-compliant with another of the related constraints).
More recently developed constraint solvers use both decision procedures and ILP (Integer Linear Programming) techniques to generate stimulus streams satisfying two or more related constraints. The combination of decision procedure and ILP technique works well with multiple related constraints that are loosely dependent on each other (i.e., where most stimulus stream modifications entered to satisfy one related constraint typically does not cause non-compliance with other related constraints). However, this simple approach doesn't work well in cases where a stimulus stream must comply with multiple related constraints that are more significantly dependent on each other, and typically fails in cases where a stimulus stream is subject to multi-dimensional constraints (e.g., one or more time/row constraints and one or more node/column constraints or diagonal constraints). Conventional constraint solvers that use decision procedures and ILP techniques are typically able to efficiently generate stimulus streams complying with one or more constraints of the same one-dimensional type (i.e., two or more time/row constraints, two or more node/column constraints, or two or more diagonal constraints). However, when faced with the task of generating stimulus streams that comply with multi-dimensional constraint (referred herein to as a multi-dimensional constraint problem), the approach utilized by conventional constraint solvers (i.e., using decision procedures and ILP techniques) causes an excessively large number of backtracks in the decision procedure by using the ILP solver to revise test vector values for one type of constraint (e.g., column constraints) without considering the revision's effect on constraint types (e.g., row or diagonal constraints). The large number of backtracks occur because solving a stimulus stream to comply with one constraint type is likely to create non-conformance with the other constraint types. Accordingly, conventional constraint solvers that use both decision procedures and ILP techniques require a long period of time to generate test vectors that satisfy multi-dimensional constraints, thereby delaying circuit design development and increasing overall production costs.
What is needed is a constraint solver and associated methods capable of automatically generating stimulus streams that comply with multi-dimensional constraints in a short amount of time. In particular, what is needed is multi-dimensional constraint solver for EDA software tools capable of quickly generating multiple different stimulus streams for use in constrained random test-type simulation processes during functional verification of circuit designs.